Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two

摘要

We consider the problem of constructing fast and small binary adder circuits.Among widely-used adders, the Kogge-Stone adder is often considered thefastest, because it computes the carry bits for two $n$-bit numbers (where $n$is a power of two) with a depth of $2\log_2 n$ logic gates, size $4 n\log_2 n$,and all fan-outs bounded by two. Fan-outs of more than two are avoided, becausethey lead to the insertion of repeaters for repowering the signal andadditional depth in the physical implementation. However, the depth bound ofthe Kogge-Stone adder is off by a factor of two from the lower bound of $\log_2n$. This bound is achieved asymptotically in two separate constructions byBrent and Krapchenko. Brent's construction gives neither a bound on the fan-outnor the size, while Krapchenko's adder has linear size, but can have up tolinear fan-out. With a fan-out bound of two, neither construction achieves adepth of less than $2 \log_2 n$. In a further approach, Brent and Kung proposedan adder with linear size and fan-out two, but twice the depth of theKogge-Stone adder. These results are 33-43 years old and no substantialtheoretical improvement for has been made since then. In this paper we integrate the individual advantages of all previous addercircuits into a new family of full adders, the first to improve on the depthbound of $2\log_2 n$ while maintaining a fan-out bound of two. Our addersachieve an asymptotically optimum logic gate depth of $\log_2 n + o(\log_2 n)$and linear size $\mathcal {O}(n)$.